package com.demo.java.OD551_600.OD597;

import java.util.Scanner;
import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【污染水域(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146586543
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 将输入的字符串按照逗号分割，得到一个字符串数组
        String[] input_str = in.nextLine().split(",");
        // 计算矩阵的大小N
        int N = (int) Math.sqrt(input_str.length);
        int[][] matrix = new int[N][N];

        // 将输入的字符串数组转换为二维矩阵
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(input_str[j + i * N]);
            }
        }

        // 使用队列（Queue）来进行BFS
        Queue<int[]> queue = new ArrayDeque<>();
        // 将所有水源（值为1的地方）加入队列
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        // 如果没有水源或者矩阵全是水源，直接返回-1
        if (queue.size() == 0 || queue.size() == N * N) {
            System.out.println(-1);
            return;
        }

        int[] node = null;
        // BFS扩散过程
        while (!queue.isEmpty()) {
            node = queue.poll();
            int x = node[0], y = node[1];

            // 上
            if (x + 1 < N && matrix[x + 1][y] == 0) {
                matrix[x + 1][y] = matrix[x][y] + 1;
                queue.offer(new int[]{x + 1, y});
            }
            // 右
            if (y + 1 < N && matrix[x][y + 1] == 0) {
                matrix[x][y + 1] = matrix[x][y] + 1;
                queue.offer(new int[]{x, y + 1});
            }
            // 下
            if (x - 1 >= 0 && matrix[x - 1][y] == 0) {
                matrix[x - 1][y] = matrix[x][y] + 1;
                queue.offer(new int[]{x - 1, y});
            }
            // 左
            if (y - 1 >= 0 && matrix[x][y - 1] == 0) {
                matrix[x][y - 1] = matrix[x][y] + 1;
                queue.offer(new int[]{x, y - 1});
            }
        }

        // 输出最后一个水源的值减1，即为需要的最小天数
        System.out.println(matrix[node[0]][node[1]] - 1);
    }
}